package com.xinwei.leetcode.数组;

import java.util.HashSet;
import java.util.Set;

// https://leetcode-cn.com/problems/missing-number/
public class _268_丢失的数字 {
    // 使用hashset
    public int missingNumber(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            set.add(nums[i]);
        }
        int missing = -1;
        for (int i = 0; i <= n; i++) {
            if (!set.contains(i)) {
                missing = i;
                break;
            }
        }
        return missing;
    }

    // 使用异或运算  因为a^a=0, a^0=a,所以最后的a就是只有一个的数字
    public int missingNumber1(int[] nums) {
        int a = 0;
        for (int i = 0; i < nums.length; i++) {
            a = a ^ nums[i];
        }
        for (int i = 0; i <= nums.length; i++) {
            a = a ^ i;
        }
        return a;

    }
}
